/*
 * @lc app=leetcode.cn id=51 lang=typescript
 *
 * [51] N 皇后
 */

// @lc code=start

//  思想：回溯法
//  遍历每一行，isValid判断当前位置是否可以放置Q
//  参考：https://www.bilibili.com/video/BV1P5411N7Xc

//  复杂度：O(n!) O(n)

function solveNQueens(n: number): string[][] {
    const res: any = []
    const board = Array.from(new Array(n), () => new Array(n).fill('.'))

    const isValid = (board: string[][], row: number, col: number): boolean => {
        // 检查列是否冲突
        for (let i = 0; i < n; i++) {
            if (board[i][col] === 'Q') return false
        }
        // 检查右上方是否冲突
        for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] === 'Q') return false
        }
        // 检查左上方是否冲突
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] === 'Q') return false
        }
        return true
    }

    const deepCopy = (arr: string[][]) => {

        let copy = []
        for (let i = 0; i < n; i++) {
            let a = arr[i].join('')
            copy.push(a)
        }
        return copy
    }

    const dfs = (board: string[][], row: number) => {
        if (row === n) {
            res.push(deepCopy(board))
            return
        }
        for (let col = 0; col < n; col++) {
            // 排除
            if (!isValid(board, row, col)) continue
            // 选择
            board[row][col] = 'Q'
            // 下一行
            dfs(board, row + 1)
            // 撤销
            board[row][col] = '.'
        }
    }

    dfs(board, 0)

    return res
};
// @lc code=end

console.log(solveNQueens(4));

